# 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
    if array is None:
        return array
    if len(array)<=1:
        return 0
    my_str = ''
    for i in array:
        my_str+=" "+str(i)
    res = []
    for i in range(len(my_str)):
        if my_str.count(my_str[i])==1:
            res.append(my_str[i])

    return res

# 更好的方法，array本身也可以count
def FindNumsAppearOnce1(self, array):
    if array is None:
        return array
    if len(array)<=1:
        return 0
    res = []
    for i in array:
        if array.count(i)==1:
            res.append(i)

    return res
# 解法2：位运算方法：
# 可以用位运算实现，如果将所有所有数字相异或，则最后的结果肯定是那两个只出现一次的数字异或
#  的结果，所以根据异或的结果1所在的最低位，把数字分成两半，每一半里都还有只出现一次的数据和成对出现的数据
#  这样继续对每一半相异或则可以分别求出两个只出现一次的数字

class Solution:
    def FindNumsAppearOnce(self, array):
        if not array:
            return []
        # 对array中的数字进行异或运算
        tmp = 0
        for i in array:
            tmp ^= i
        # 获取tmp中最低位1的位置
        idx = 0
        while (tmp & 1) == 0:
            tmp >>= 1
            idx += 1
        a = b = 0
        for i in array:
            if self.isBit(i, idx):
                a ^= i
            else:
                b ^= i
        return [a, b]

    def isBit(self, num, idx):
        """
        判断num的二进制从低到高idx位是不是1
        :param num: 数字
        :param idx: 二进制从低到高位置
        :return: num的idx位是否为1
        """
        num = num >> idx
        return num & 1